import java.util.HashMap;
import java.util.Map;

public class FruitIntoBuckets {
    // 水果成篮 https://leetcode.cn/problems/fruit-into-baskets/description/

    // 哈希表版
    public int totalFruit(int[] fruits) {
        Map<Integer,Integer> map=new HashMap<Integer,Integer>();
        int ret=0;
        for(int left=0,right=0;right<fruits.length;right++) {
            int in=fruits[right];
            //getOrDefault(a,b)的意思是若a不在,则返回0(并不创建新的键值对),若存在,那么就返回对应value
            map.put(in,map.getOrDefault(in,0)+1);
            while(map.size()>2) {
                //出窗口
                int out=fruits[left];
                map.put(out,map.get(out)-1);
                if(map.get(out)==0) map.remove(out);//当元素数量减小到0时,将其删除
                left++;
            }
            //更新结果
            ret=Math.max(right-left+1,ret);
        }
        return ret;
    }

    // 数组版
    public int totalFruit1(int[] fruits) {
        int[] hash=new int[fruits.length+1];//定义数组来存储不同种类的水果的数量
        int ret=0;
        //kinds是用来标记hash数组中有多少水果种类是>0的,也就是在篮子里的
        for(int left=0,right=0,kinds=0;right<fruits.length;right++) {
            int in=fruits[right];
            if(hash[in]==0) kinds++;// 表示一种新水果被放入了篮子
            hash[in]++;//进窗口
            while(kinds>2) {
                //出窗口
                int out=fruits[left];
                hash[out]--;
                if(hash[out]==0) kinds--;//当元素数量减小到0时,将其删除
                left++;
            }
            //更新结果
            ret=Math.max(right-left+1,ret);
        }
        return ret;
    }
}
